package main

import (
	"fmt"
	"math/rand"
	"time"
)

// 数字重复统计
// 随机产生100个整数
// 数字的范围[-100, 100] [0, 201) - 100
// 降序输出这些生成的数字并打印其重复的次数

func quickSort(a []int, left int, right int) {
	if left >= right {
		return
	}
	i := left
	j := right
	for i != j {
		for i < j && a[left] <= a[j] {
			j--
		}
		for i < j && a[left] >= a[i] {
			i++
		}
		a[i], a[j] = a[j], a[i] // 以 i为分界，左边的比a[left]小
		// 右边的比 a[left]大
		// go 语言交换不用临时变量
	}
	a[i], a[left] = a[left], a[i] // 再交换 a[left]和a[i]

	quickSort(a, left, i-1) // 分治思想
	quickSort(a, i+1, right)
}

func main() {
	a := make([]int, 200)
	m := make(map[int]int, 300)
	gen := rand.New(rand.NewSource(time.Now().UnixNano()))
	for i := 0; i < 100; i++ {
		a[i] = gen.Intn(201) - 100
		m[a[i]]++
	}
	//sort.Ints(a)
	quickSort(a, 0, 99)
	for i := 99; i >= 0; i-- {
		fmt.Printf("%d 重复次数: %d\n", a[i], m[a[i]])
	}
}
